Field of the Invention
This invention relates generally to the field of data communications. More particularly, this invention relates to a method and apparatus for management of queue memory in an internetworking communication processor handling messages of differing priorities and transmission media of differing speeds.
In a communication system which utilizes a single queue to service transmitters of varying speed, a simple first-in-first-out queue can result in inefficient utilization of the transmission media. This is due to the fact that high speed transmitters can empty the queue faster than low speed transmitters. Consequently, a large stream of data packets destined for a low speed transmitter can fill up the queue and prohibit new packets destined for the high speed transmitter from being loaded into the queue, even though those high speed transmitters may be idle. Although this problem can be eased somewhat by using more memory for queuing purposes, this is an expensive alternative.
The present invention addresses this problem in a communications processor which, in the preferred embodiment, is used to link various local area networks (LAN's) together using wide area network (WAN) links of varying speeds. Such an internetworking communications processor is commercially available from RACAL-MILGO as its RACALAN NETEXPRESS.TM. communications processor which may be described as a MAC layer Bridge. This product is described in a document entitled "LAN Internetworking: The Next Evolutionary Step--A White Paper by Racal-Milgo", 1990 Racal-Milgo, which is hereby incorporated by reference. (The present invention was developed as an enhancement to this product and has not been put into the commercial product as of the filing date of this application.)
The present invention may also be applicable to more conventional bridges, gateways, routers, multiplexers and the like. A single buffer and queue arrangement is shared among the various output ports coupled to the wide area network links of the present invention. The speed of these ports can vary widely. Thus it is desirable to assure that the high speed links are not slowed down and rendered inefficient by queue overuse from low speed links. It is also desirable to assure that high priority packets used to manage the network are not discarded due to queues filled with lower priority packets. The present invention addresses these problems by use of a prioritization scheme for the packets and a loadsheding routine for determining when to load packets into the queue.